#include <iostream>
using namespace std;

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

ListNode* createLinkedList(int arr[], int n){

    if(n == 0)
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for(int i = 1 ; i < n ; i ++){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

void printLinkedList(ListNode* head){

    if(head == NULL){
        cout<<"NULL"<<endl;
        return;
    }

    ListNode* curNode = head;
    while(curNode != NULL){
        cout << curNode->val;
        if(curNode->next != NULL)
            cout << " -> ";
        curNode = curNode->next;
    }

    cout << endl;

    return;
}

void deleteLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != NULL){
        ListNode* delNode = curNode;
        curNode = curNode->next;
        delete delNode;
    }

    return;
}

// 24. Swap Nodes in Pairs
// https://leetcode.com/problems/swap-nodes-in-pairs/description/

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        ListNode *h = new ListNode(0), *r;    // 结果链表的头指针和尾指针
        r = h;  // 初始化尾指针
        ListNode *oldr, *p, *q;

        p = head;   // 从第1个节点开始遍历
        while(p != NULL) {
            oldr = r;
            // 插入奇数序号的结点p
            r->next = p; r = p;
            p = p->next;
            if(p != NULL) {
                q = p->next;    // 先记录下一个结点
                // 插入偶数序号的结点p
                p->next = r;   // p->next = r;
                oldr->next = p;
//                r = p;
                p = q;
            }
            r->next = NULL;
        }

        return h->next; // 返回交换后的链表
    }
};

int main() {
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(int);

    ListNode* head = createLinkedList(arr, n);
    printLinkedList(head);

    head = Solution().swapPairs(head);
    printLinkedList(head);

    deleteLinkedList(head);
}
